package Demo9;

// 排序类，包含快速排序和归并排序的实现
public class Sorting {
    /**
     * 快速排序主方法
     *
     * @param array       要排序的数组
     * @param start       起始索引
     * @param end         结束索引
     * @param comparisons 比较次数计数
     * @param movements   移动次数计数
     */
    public static void quickSort(int[] array, int start, int end, int[] comparisons, int[] movements) {
        if (start >= end) {
            return;
        }
        int pivotIndex = partition(array, start, end, comparisons, movements);
        quickSort(array, start, pivotIndex, comparisons, movements);
        quickSort(array, pivotIndex + 1, end, comparisons, movements);
    }

    /**
     * 分区方法，返回基准元素的位置
     *
     * @param array       要排序的数组
     * @param low         起始索引
     * @param high        结束索引
     * @param comparisons 比较次数计数
     * @param movements   移动次数计数
     * @return 基准元素的位置
     */

    private static int partition(int[] array, int low, int high, int[] comparisons, int[] movements) {
        int pivot = array[low]; // 将第一个元素作为基准
        int start = low;
        int right = high;

        while (start < right) {
            // 从右向左找第一个小于基准的元素
            while (start < right && array[right] >= pivot) {
                right--;
                comparisons[0]++;
            }
            // 找到后交换
            if (start < right) {
                array[start] = array[right];
                start++;
                movements[0]++;
            }

            // 从左往右找第一个大于基准的元素
            while (start < right && array[start] <= pivot) {
                start++;
                comparisons[0]++;
            }
            // 找到后交换
            if (start < right) {
                array[right] = array[start];
                right--;
                movements[0]++;
            }
        }

        // 将基准元素放到最终位置
        array[start] = pivot;
        movements[0]++;
        return start;
    }

    /**
     * 归并排序主方法
     *
     * @param array       要排序的数组
     * @param start       起始索引
     * @param end         结束索引
     * @param comparisons 比较次数计数
     * @param movements   移动次数计数
     */
    public static void mergeSort(int[] array, int start, int end, int[] comparisons, int[] movements) {
        if (start >= end) {
            return;
        }

        int mid = start + (end - start) / 2;

        // 递归排序左半部分
        mergeSort(array, start, mid, comparisons, movements);

        // 递归排序右半部分
        mergeSort(array, mid + 1, end, comparisons, movements);

        // 合并
        merge(array, start, mid, end, comparisons, movements);
    }

    /**
     * 合并方法
     *
     * @param array       要排序的数组
     * @param start       起始索引
     * @param mid         中间索引
     * @param end         结束索引
     * @param comparisons 比较次数计数
     * @param movements   移动次数计数
     */
    private static void merge(int[] array, int start, int mid, int end, int[] comparisons, int[] movements) {
        int start1 = start;
        int start2 = mid + 1;

        int[] tempArr = new int[end - start + 1];
        int k = 0; // 临时数组的索引下标

        // 排序 合并到临时数组
        while (start1 <= mid && start2 <= end) {
            comparisons[0]++;
            if (array[start1] <= array[start2]) {
                tempArr[k] = array[start1];
                start1++;
            } else {
                tempArr[k] = array[start2];
                start2++;
            }
            k++;
            movements[0]++;
        }

        // 处理剩余的数组
        while (start1 <= mid) {
            tempArr[k++] = array[start1++];
            movements[0]++;
        }
        while (start2 <= end) {
            tempArr[k++] = array[start2++];
            movements[0]++;
        }

        // 将临时数组的元素 赋值回原数组
        for (int i = 0; i < tempArr.length; i++) {
            array[i + start] = tempArr[i];
            movements[0]++;
        }
    }
}
